home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / mawk10.zip / REXP0.C < prev    next >
C/C++ Source or Header  |  1991-10-05  |  11KB  |  453 lines
  1.  
  2. /********************************************
  3. rexp0.c
  4. copyright 1991, Michael D. Brennan
  5.  
  6. This is a source file for mawk, an implementation of
  7. the AWK programming language.
  8.  
  9. Mawk is distributed without warranty under the terms of
  10. the GNU General Public License, version 2, 1991.
  11. ********************************************/
  12.  
  13. /*$Log:    rexp0.c,v $
  14.  * Revision 3.4  91/08/13  09:10:05  brennan
  15.  * VERSION .9994
  16.  * 
  17.  * Revision 3.3  91/07/19  07:29:24  brennan
  18.  * backslash at end of regular expression now stands for backslash
  19.  * 
  20.  * Revision 3.2  91/07/19  06:58:23  brennan
  21.  * removed small bozo in processing of escape characters
  22.  * 
  23.  * Revision 3.1  91/06/07  10:33:20  brennan
  24.  * VERSION 0.995
  25.  * 
  26.  * Revision 1.2  91/06/05  08:59:36  brennan
  27.  * changed RE_free to free
  28.  * 
  29.  * Revision 1.1  91/06/03  07:10:15  brennan
  30.  * Initial revision
  31.  * 
  32. */
  33.  
  34. /*  lexical scanner  */
  35.  
  36. #include  "rexp.h"
  37.  
  38. /* static functions */
  39. static int  PROTO( do_str, (int, char **, MACHINE *) ) ;
  40. static int  PROTO( do_class, (char **, MACHINE *) ) ;
  41. static int  PROTO( escape, (char **) ) ;
  42. static BV   *PROTO( store_bvp, (BV *) ) ;
  43. static int  PROTO( ctohex, (int) ) ;
  44.  
  45.  
  46. #ifndef  EG  /* if EG make next array visible */
  47. static
  48. #endif
  49. char  RE_char2token[ '|' + 1 ] = {
  50. 0,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  51. 13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,9,13,13,13,
  52. 6,7,3,4,13,13,10,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  53. 13,13,5,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  54. 13,13,13,13,13,13,13,13,13,13,11,12,13,8,13,13,13,13,13,13,
  55. 13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  56. 13,13,13,13,1} ;
  57.  
  58. #define  char2token(x) ( (unsigned char)(x) > '|' ? T_CHAR : RE_char2token[x] )
  59.  
  60. #define NOT_STARTED    (-1)
  61.  
  62. static  int  prev  ;
  63. static  char   *lp  ;     /*  ptr to reg exp string  */
  64. static  unsigned re_len ;
  65.  
  66.  
  67. void  RE_lex_init( re )
  68.   char *re ;
  69. { 
  70.   lp = re ;
  71.   re_len = strlen(re) + 1  ;
  72.   prev = NOT_STARTED ;
  73.   RE_run_stack_init() ;
  74. }
  75.   
  76.  
  77. int   RE_lex( mp )
  78.   MACHINE  *mp ;
  79. { register int c ;
  80.  
  81.   switch( c = char2token(*lp) )
  82.    {
  83.      case T_OR :
  84.      case T_PLUS :
  85.      case T_STAR :
  86.      case T_Q :
  87.      case T_RP :
  88.            lp++ ;  return  prev = c ;
  89.      case T_SLASH :
  90.            break ;
  91.  
  92.      case 0   :   return 0 ;
  93.      
  94.      case T_LP :
  95.            switch( prev )
  96.            { 
  97.              case T_CHAR :
  98.              case T_STR  :
  99.              case T_ANY :
  100.              case T_CLASS :
  101.              case T_START :
  102.              case T_RP :
  103.              case T_PLUS :
  104.              case T_STAR :
  105.              case T_Q :
  106.              case T_U :
  107.                   return prev = T_CAT ;
  108.              default  :
  109.                   lp++ ;
  110.                   return prev = T_LP ;
  111.            }
  112.    }
  113.  
  114.   /*  *lp  is  an operand, but implicit cat op is possible   */
  115.   switch( prev )
  116.    { case  NOT_STARTED :
  117.      case  T_OR :
  118.      case  T_LP :
  119.      case T_CAT :
  120.  
  121.           switch( c )
  122.            { case  T_ANY : 
  123.              { static plus_is_star_flag = 0 ;
  124.  
  125.                   if ( * ++lp == '*' )
  126.                   { lp++ ;  *mp = RE_u() ;
  127.                     return  prev = T_U ; }
  128.                   else
  129.                   if ( *lp == '+' )
  130.                       if ( plus_is_star_flag )
  131.                       { lp++ ;  *mp = RE_u() ;
  132.                         plus_is_star_flag = 0 ;
  133.                         return prev = T_U ;
  134.                       }
  135.                       else
  136.                       { plus_is_star_flag = 1 ;
  137.                         lp-- ; *mp = RE_any() ;
  138.                         return prev = T_ANY ;
  139.                       }
  140.                   else  
  141.                   { *mp = RE_any() ;
  142.                     prev = T_ANY ;
  143.                   }
  144.               }
  145.               break ;
  146.                     
  147.              case  T_SLASH :
  148.                   lp++ ; c = escape(&lp) ;
  149.                   prev = do_str(c, &lp, mp) ;
  150.                   break ;
  151.  
  152.              case  T_CHAR  :
  153.                   c = *lp++ ;
  154.                   prev = do_str(c, &lp, mp) ;
  155.                   break ;
  156.  
  157.              case T_CLASS : prev = do_class(&lp, mp) ;
  158.                             break ;
  159.  
  160.              case T_START : *mp = RE_start() ; lp++ ;
  161.                             prev = T_START ;
  162.                             break ;
  163.  
  164.              case T_END :  
  165.                      lp++ ; *mp = RE_end() ;
  166.                      return  prev = T_END ;
  167.  
  168.              default :
  169.                      RE_panic("bad switch in RE_lex") ;
  170.            }
  171.            break ;
  172.  
  173.      default : /* don't advance the pointer, return T_CAT */
  174.           return prev = T_CAT ;
  175.     }
  176.     /* check for end character */
  177.     if ( *lp == '$' )
  178.     { mp->start->type += END_ON ; lp++ ; }
  179.     return prev ;
  180. }
  181.  
  182. static  int  do_str( c, pp, mp)
  183.   int c ; /* the first character */
  184.   char **pp ;  /* where to put the re_char pointer on exit */
  185.   MACHINE  *mp ;  /* where to put the string machine */
  186. { register char *p , *s ;
  187.   char *str ;
  188.   unsigned len ;
  189.  
  190.  
  191.   p = *pp ;
  192.   s = str = RE_malloc( re_len ) ;
  193.   *s++ = c ;  len = 1 ;
  194.  
  195.   while ( 1 )
  196.   { char *save ;
  197.   
  198.     switch( char2token(*p) )
  199.     {
  200.       case  T_CHAR :  *s++ = *p++ ;
  201.                       break ;
  202.       case  T_SLASH :
  203.                       save = ++p ;
  204.                       *s++ = escape(&save) ;
  205.                       p = save ;
  206.                       break ;
  207.  
  208.       default  :  goto  out ;
  209.     }
  210.     len++ ;
  211.   }
  212. out:
  213.   /* if len > 1 and we failed on a ? + or * , need to back up */
  214.   if ( len > 1 && (*p == '*' || *p == '+' || *p == '?' ) )
  215.   { len-- ; p-- ; s-- ; }
  216.  
  217.   *s = 0 ;
  218.   *pp = p ;
  219.   *mp = RE_str((char *) RE_realloc(str, len+1) , len) ;
  220.   return  T_STR ;
  221. }
  222.  
  223.  
  224. /*--------------------------------------------
  225.   BUILD A CHARACTER CLASS
  226.  *---------------------------*/
  227.  
  228. #define  on( b, x)  ( (b)[(x)>>3] |= ( 1 << ((x)&7) ))
  229.  
  230. static  void  PROTO(block_on, (BV,int,int) ) ;
  231.  
  232. static  void  block_on( b, x, y)
  233.   BV b ; int x, y ;  /* must call with x<=y */
  234. { int lo = x >> 3 ;
  235.   int hi = y >> 3 ;
  236.   int  i, j, bit  ;
  237.  
  238.   if ( lo == hi )
  239.     { j = x&7 ; bit =  1 << j ; i = (y&7) - j + 1 ;
  240.       for ( ; i ; i-- , bit <<= 1 )  b[lo] |= bit ; }
  241.   else
  242.     { for ( i = lo + 1 ; i <= hi - 1 ; i++ )  b[i] = 0xff ;
  243.       b[lo] |= ( 0xff << (x&7) ) ;
  244.       b[hi] |= ~( 0xff << ((y&7)+1)) ;
  245.     }
  246. }
  247.  
  248. /* build a BV for a character class.
  249.    *start points at the '['
  250.    on exit:   *start points at the character after ']'
  251.               mp points at a machine that recognizes the class
  252. */
  253.  
  254. static int  do_class( start, mp)
  255.   char **start ; MACHINE  *mp ;
  256. { register char *p ;
  257.   register BV   *bvp ;
  258.   int  prev ;
  259.   char *q , *t;
  260.   int  cnt ;
  261.   int comp_flag ;
  262.  
  263.   p = (*start) + 1 ;
  264.   if ( *p == ']' || *p == '^' && *(p+1) == ']' )
  265.          RE_error_trap(-E3) ;
  266.   while ( 1 )  /* find the back of the class */
  267.     { if ( ! (q = strchr(p,']')) )  /* no closing bracket */
  268.          RE_error_trap(-E3) ;
  269.       p = q-1 ;
  270.       cnt = 0 ;
  271.       while ( *p == '\\') { cnt++ ; p-- ; }
  272.       if ( (cnt & 1) == 0 )  /* even number of \ */  break ;
  273.       p = q+1 ;
  274.     }
  275.   /*  q  now  pts at the back of the class   */
  276.   p = (*start) + 1 ;
  277.   *start = q + 1 ;
  278.  
  279.   bvp = (BV *) RE_malloc( sizeof(BV) ) ;
  280.   (void) memset( bvp, 0, SIZE_T(sizeof(BV)) ) ;
  281.  
  282.   comp_flag = *p == '^' ? p++ , 1 : 0 ;
  283.   prev = -1 ;  /* indicates  -  cannot be part of a range  */
  284.  
  285.   while ( p < q )
  286.   {
  287.      switch( *p )
  288.       { case '\\' :
  289.           t = ++p ;
  290.           prev = escape(&t) ;
  291.           on(*bvp, prev) ;
  292.           p = t ;
  293.           continue ;
  294.  
  295.         case '-' :
  296.           if ( prev == -1 || p+1 == q || prev > *(p+1) )
  297.              { prev = '-' ; on(*bvp, '-') ; }
  298.           else
  299.              { p++ ;
  300.                block_on(*bvp, prev, *p) ;
  301.                prev = -1 ;
  302.              }
  303.           break ;
  304.  
  305.         default :
  306.           prev = *p ;
  307.           on(*bvp, *p) ;
  308.           break ;
  309.       }
  310.       p++ ;
  311.   }
  312.  
  313.   if ( comp_flag )
  314.     for ( p = (char *) bvp ; p < (char *) bvp + sizeof(BV) ; p++)  *p = ~*p ;
  315.  
  316.   /* make sure zero is off */
  317.   (*bvp)[0] &= 0xfe ;
  318.  
  319.   *mp = RE_class( store_bvp( bvp ) ) ;
  320.   return  T_CLASS ;
  321. }
  322.  
  323.  
  324. /* storage for bit vectors so they can be reused ,
  325.    stored in an unsorted linear array 
  326.    the array grows as needed
  327. */
  328.  
  329. #define         BV_GROWTH       6
  330.  
  331. static BV *store_bvp( bvp )
  332.   BV *bvp ;
  333. {
  334.   static BV **bv_base, **bv_limit ;
  335.   static BV **bv_next ; /* next empty slot in the array */
  336.  
  337.   register BV **p ;
  338.   unsigned t ;
  339.  
  340.  
  341.   if ( bv_next == bv_limit ) /* need to grow */
  342.   {
  343.     if ( ! bv_base )  /* first growth */
  344.     {  t = 0 ; bv_base = (BV**)RE_malloc(BV_GROWTH*sizeof(BV*)) ; }
  345.     else 
  346.     { t = bv_next - bv_base ;
  347.       bv_base = (BV**) RE_realloc(bv_base, (t+BV_GROWTH)*sizeof(BV*)) ;
  348.     }
  349.  
  350.     bv_next = bv_base + t ;
  351.     bv_limit = bv_next + BV_GROWTH ;
  352.   }
  353.  
  354.   /* put bvp in bv_next as a sentinal */
  355.   *bv_next = bvp ;
  356.   p = bv_base ;
  357.   while ( memcmp(*p, bvp, SIZE_T(sizeof(BV))) )  p++ ;
  358.  
  359.   if ( p == bv_next )  /* it is new */
  360.         bv_next++ ;
  361.   else  /* we already have it */  free(bvp) ;
  362.  
  363.   return *p ;
  364. }
  365.   
  366.  
  367. /* ----------   convert escape sequences  -------------*/
  368.  
  369. #define isoctal(x)  ((x)>='0'&&(x)<='7')
  370.  
  371. #define  NOT_HEX        16
  372. static char hex_val['f' - 'A' + 1] = {
  373. 10,11,12,13,14,15, 0, 0,
  374.  0, 0, 0, 0, 0, 0, 0, 0,
  375.  0, 0, 0, 0, 0, 0, 0, 0,
  376.  0, 0, 0, 0, 0, 0, 0, 0,
  377. 10,11,12,13,14,15 } ;
  378.  
  379. /* interpret 1 character as hex */
  380. static int ctohex( c )
  381.   register int c ;
  382. { int t ;
  383.  
  384.   if ( c >= '0' && c <= '9' )  return c - '0' ;
  385.  
  386.   if ( c >= 'A' && c <= 'f' && ( t = hex_val[c-'A'] ))  return t ;
  387.  
  388.   return NOT_HEX ;
  389. }
  390.  
  391. #define  ET_END     7
  392.  
  393. static struct { char in , out ; } escape_test[ET_END+1] = {
  394. 'n' , '\n',
  395. 't' , '\t',
  396. 'f' , '\f',
  397. 'b' , '\b',
  398. 'r' , '\r',
  399. 'a' , '\07',
  400. 'v' , '\013',
  401. 0 , 0 } ;
  402.  
  403.  
  404. /*-----------------
  405.   return the char 
  406.   and move the pointer forward
  407.   on entry *s -> at the character after the slash
  408.  *-------------------*/
  409.  
  410. static int escape(start_p)
  411.   char **start_p ;
  412. { register char *p = *start_p ;
  413.   register unsigned x ;
  414.   unsigned xx ;
  415.   int i ;
  416.  
  417.   
  418.   escape_test[ET_END].in = *p ;
  419.   i = 0 ;
  420.   while ( escape_test[i].in != *p ) i++ ;
  421.   if ( i != ET_END )  /* in table */
  422.   { *start_p = p + 1 ;
  423.     return  escape_test[i].out ;
  424.   }
  425.  
  426.   if ( isoctal(*p) )
  427.   { x = *p++ - '0' ;
  428.     if ( isoctal(*p) )
  429.     { x = (x<<3) + *p++ - '0' ;
  430.       if ( isoctal(*p) )
  431.          x = (x<<3) + *p++ - '0' ;
  432.     }
  433.     *start_p = p ;
  434.     return  x & 0xff ;
  435.   }
  436.  
  437.   if ( *p == 0 )  return '\\' ;
  438.  
  439.   if ( *p++ == 'x' ) /* might be a hex digit */
  440.   {  if ( (x = ctohex(*p)) == NOT_HEX ) 
  441.      { *start_p  = p ;  return 'x' ; }
  442.  
  443.      /* look for another hex digit */
  444.      if ( (xx = ctohex(* ++p)) != NOT_HEX )
  445.      { x = (x<<4) + xx ; p++ ; }
  446.  
  447.      *start_p = p ; return x ;
  448.   }
  449.   /* anything else \c -> c */
  450.   *start_p = p ;
  451.   return p[-1]  ;
  452. }
  453.